home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / signature.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-12-03  |  3.2 KB  |  149 lines  |  [TEXT/R*ch]
  1. /*
  2.  * Module: signature.c
  3.  * Purpose: The main signature algorithm
  4.  * Routines;
  5.  * pcover signature():
  6.  *    Entry point for the signature cubes algorithm.    
  7.  * pcover generate_primes():
  8.  *    Generates the set of primes corresponding to 
  9.  *    the Essential Signature Cubes
  10.  */
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <signal.h>
  15. #include "espresso.h"
  16. #include "signature.h"
  17.  
  18. static long start_time; /* yuk */
  19.  
  20. pcover
  21. signature(F1, D1, R1)
  22. pcover F1, D1, R1;
  23. {
  24.     pcover ESC,ESSet,ESSENTIAL;
  25.     pcover F,D,R;
  26.     pcube last,p;
  27.  
  28.     /* make scratch copy */
  29.     F = sf_save(F1);
  30.     D = sf_save(D1);
  31.     R = sf_save(R1);
  32.  
  33.     /* unwrap offset */
  34.     R = unravel(R, cube.num_binary_vars);
  35.     R = sf_contain(R);
  36.  
  37. //    signal(SIGXCPU,cleanup);
  38.     start_time = ptime();
  39.  
  40.     /* Initial expand and irredundant */
  41.     foreach_set(F, last, p) {
  42.         RESET(p, PRIME);
  43.     }
  44.  
  45.     S_EXECUTE(F = expand(F, R, FALSE), ESSEN_TIME);
  46.     S_EXECUTE(F = irredundant(F, D), ESSEN_TIME);
  47.     S_EXECUTE(ESSENTIAL = essential(&F,&D), ESSEN_TIME);
  48.  
  49.     S_EXECUTE(ESC = find_canonical_cover(F,D,R), FCC_TIME);
  50.     /**************************************************
  51.     printf("ESCubes %d\n", ESC->count + ESSENTIAL->count);
  52.     fflush(stdout);
  53.     **************************************************/
  54.  
  55.     S_EXECUTE(ESSet = generate_primes(ESC,R), PRIMES_TIME);
  56.     /**************************************************
  57.     printf("ESSet %d\n",ESSet->count + ESSENTIAL->count);
  58.     fflush(stdout);
  59.     **************************************************/
  60.  
  61.     S_EXECUTE(F = signature_minimize_exact(ESC,ESSet), MINCOV_TIME);
  62.     sf_append(F,ESSENTIAL);
  63.     /**************************************************
  64.     printf("Exact_Minimum %d\n",F->count);
  65.     print_cover(F,"Exact Minimum");
  66.     **************************************************/
  67.  
  68.     if (! skip_make_sparse && R != 0) {
  69.         F = make_sparse(F, D1, R);
  70.     }
  71.  
  72.     free_cover(D);
  73.     free_cover(R);
  74.     free_cover(ESC);
  75.     free_cover(ESSet);
  76.     return F;
  77. }
  78.  
  79.  
  80. pcover
  81. generate_primes(F,R)
  82. pcover F,R;
  83. {
  84.     pcube c,r,lastc,b,lastb;
  85.     pcover BB,PRIMES;
  86.     pcube odd,even,out_part_r;
  87.     register int i;
  88.         register int w, last;
  89.     register unsigned int x;
  90.     int count;
  91.  
  92.     out_part_r = new_cube();
  93.     odd = new_cube();
  94.     even = new_cube();
  95.  
  96.     count = 0;
  97.     PRIMES = new_cover(F->count);
  98.     foreach_set(F,lastc,c){
  99.         BB = new_cover(R->count);
  100.         BB->count = R->count;
  101.         /* BB = get_blocking_matrix(R,c); */
  102.         foreachi_set(R,i,r){
  103.             b = GETSET(BB,i);
  104.             if ((last = cube.inword) != -1) {
  105.                 /* Check the partial word of binary variables */
  106.                 x = r[last] & c[last];
  107.                 x = ~(x | x >> 1) & cube.inmask;
  108.                 b[last] = r[last] & (x | x << 1);
  109.                 /* Check the full words of binary variables */
  110.                 for(w = 1; w < last; w++) {
  111.                         x = r[w] & c[w];
  112.                         x = ~(x | x >> 1) & DISJOINT;
  113.                     b[w] = r[w] & (x | x << 1);
  114.                 }
  115.                 }
  116.             PUTLOOP(b,LOOP(r));
  117.             INLINEset_and(b,b,cube.binary_mask);
  118.             INLINEset_and(out_part_r,cube.mv_mask,r);
  119.             if(!setp_implies(out_part_r,c)){
  120.                 INLINEset_or(b,b,out_part_r);
  121.             }
  122.         }
  123.         BB = unate_compl(BB);
  124.         if(BB != NULL){
  125.             foreach_set(BB,lastb,b){
  126.                 set_not(b);
  127.             }
  128.             sf_append(PRIMES,BB);
  129.         }
  130.         count++;
  131.         if(count % 100 == 0){
  132.             PRIMES = sf_contain(PRIMES);
  133.         }
  134.     }
  135.     PRIMES = sf_contain(PRIMES);
  136.     free_cube(out_part_r);
  137.     free_cube(odd);
  138.     free_cube(even);
  139.     return PRIMES;
  140. }
  141.  
  142. void
  143. cleanup()
  144. {
  145.     s_runtime(ptime() - start_time);    
  146.     printf("CPU Limit Exceeded\n");
  147.     exit(1);
  148. }
  149.